1. Field of the Invention
The present invention generally relates to cache resources for computer systems.
2. Description of the Related Art
Data within computing environments may be cached to high speed devices to improve performance. FLASH memory is well suited for use as a high speed cache device, but unlike RAM or disk drives FLASH memory wears out with repeated write/erase operations. Therefore it is highly advantageous to minimize the number of writes to the FLASH based cache device as well as to only write data to a flash based cache device if it is highly probable that the data will be accessed again.
Caches must be populated with data before they can begin to offload data accesses from slower devices. This involves copying data from the slower device being cached and writing to the higher speed cache device. Unfortunately, although the read performance of FLASH based devices makes them very desirable for use as a cache, FLASH devices wear out with multiple write/erase cycles. Therefore it is advantageous to write data to a FLASH based cache device only if it has a high probability of being accessed again, and it is also advantageous to prevent data being written to the cache device if it is never going to be accessed again.
Traditional general purpose caches use many different algorithms to select data to be cached, and often combine multiple algorithms, sometimes employing adaptive feedback mechanisms. Typical algorithms include, but are not limited to Most Frequently Used (MFU) algorithms that keep counts of how often data is accessed, Most Recently Used (MRU) algorithms that keep track of how recently data has been accessed, and Read Ahead algorithms, that look for sequential patterns in data accesses. When multiple algorithms are used to manage what data is kept in the cache, lists of items that were previously in the cache may be maintained to provide dynamic feedback for selection between caching algorithms or the allocation of caching resources between caching algorithms. These lists of data that have been evicted and are no longer in the cache are often called “shadow” or “ghost” lists.
Traditional caches have been architected around devices that do not appreciably wear out with repeated write/erase cycles, such as Dynamic Random Access Memory (DRAM) or Static Random Access Memory (SRAM) in the case of the block caches of most modern operating systems. In such cases the penalty for writing data to the cache when it will never be accessed again is quite small and little or nothing is done to avoid this occurrence. Another example is the disk based caches used to improve the performance of tape libraries in Hierarchical Storage Management systems (HSMs), where there is no concern over wearing out the disk drives. In these caching applications data is usually entered into the cache device as soon as it is accessed.
Traditional caching algorithms typically provide an “aging” mechanism to evict data from the cache relatively quickly if it is not accessed again. “Shadow” or “ghost” lists are typically implemented in the same manner as the cache algorithm they correspond to, so that if a cache implemented both MRU and MFU algorithms, there would be both MRU and MFU “shadow” or “ghost” lists. The “shadow” or “ghost” lists are aged in the same way as the caches algorithms they represent are, and provide feedback as to how the corresponding algorithm would have performed if it had been allocated more caching resources.
General definitions for terms utilized in the pertinent art are set forth below.
Application Programming Interface (API) is a collection of computer software code, usually a set of class definitions, that can perform a set of related complex tasks, but has a limited set of controls that may be manipulated by other software-code entities. The set of controls is deliberately limited for the sake of clarity and ease of use, so that programmers do not have to work with the detail contained within the given API itself.
“Cache” refers to the memory in which data is stored in order to make the data more readily and speedily accessible, transparently. When a cache is exhausted, it is flushed of data, to be replaced with the next cache according to a replacement algorithm.
“Cached data” is data in cache memory duplicating original values stored elsewhere (such as the hard disk) on a computer.
“Cache hit” refers to when the processor looks for data in cache memory and finds the data. A cache hit places less strain on input/output (I/O) resources and limited network resources.
“Cache miss” refers to when the processor looks for data in cache memory and finds that it is not there, resulting in having to read from the main memory or hard disk. Data retrieved during a cache miss is often written into the cache in anticipation of further need for it.
“Caching resources” refers to the physical or virtual components of limited availability required for caches or the process of caching, such as memory or a processing unit.
“Cloud computing” is generally defined as using computing resources, primarily servers, owned by a third party provider (such as the AMAZON ELASTIC COMPUTE CLOUD, JOYENT, and GOOGLE APPS) such that the user does not need to make a substantial investment in computer hardware and scale resources depending on the user's needs. Cloud computing primarily involves Web applications but can include storage, raw computing and other specialized services.
Compatibility library is a software program that provides an interface between computer programs, and in particular an interface that provides an interface between a proprietary environment and an open source or GNU GPL device driver that provides the supporting functionality for the device driver.
“Data center” is a centralized location where computing resources (such as, host computers, servers, applications, databases, or network access) critical to an organization are maintained in a highly controlled physical environment.
Device driver is a software program that allows a hardware device to interact with software installed on the hardware device.
“Execution environments” refers to operating systems or virtual machines in which executable programs are executed. When a computer program is executed, or running, a process is created.
Function pointer is a programming language data type that invokes a function in a computer memory.
Ghost list is a list of recently evicted entries from a cache maintained to be used to adapt a cache algorithm to recent changes. The ghost list does not contain the actual data but only metadata for the listed entry.
GNU, General Public License is a license for an open source operating system based on UNIX, which requires that derived works be distributed under the same license terms.
Hypervisor is a hardware virtualization technique that allows a computer to host multiple operating systems by providing a guest operating system with a virtual operating platform.
Kernel is a component of an operating system that connects a computer's software applications to the computer's hardware.
“Least Recently Used” or “LRU” cache algorithm first evicts the least recently used items on a list of cache items.
“Load balancing” refers to distributing workload across multiple computers, central processing units, or other resources, to achieve optimal resource utilization, maximize throughput, minimize response time, and avoid overload.
“Logical unit number” or “LUN” is an identification number given to logical units (devices) connected to a SCSI “Small Computer System Interface” adapter; typically, the logical disks in a storage area network (SAN).
“Mass storage devices” refers to removable or non-removable media that can store large amounts of data, such as tape drives, redundant array of independent disks (RAID), magnetic disks, or flash drives.
“Non-volatile caching device” refers to a storage device that can retain data within memory even when the device is not powered on, such as a flash drive.
“Open source software” or “OSS” refers to computer software that is available with open access to the source code (design and implementation), which is typically free.
“Process identifier”, “process ID”, or “PID” is a number used by operating systems (OS) to uniquely identify a process, an OS object that consists of an executable program, a set of virtual memory addresses, and one or more threads. When a program runs, a process is created.
“Virtualization” refers to a computer software/hardware platform that allows running several operating systems simultaneously on the same computer. VMware vSphere Hypervisor™ (ESXi) is an example of a hardware virtualization product.
“Virtualized environment” refers to hypervisor, or virtualization, systems.
Virtual Machine is a software abstraction of a physical computer.
“Web-Browser” is a complex software program, resident in a client computer, that is capable of loading and displaying text and images and exhibiting behaviors as encoded in HTML (HyperText Markup Language) from the Internet, and also from the client computer's memory. Major browsers include MICROSOFT INTERNET EXPLORER, NETSCAPE, APPLE SAFARI, MOZILLA FIREFOX, and OPERA.
“Web-Server” is a computer able to simultaneously manage many Internet information-exchange processes at the same time. Normally, server computers are more powerful than client computers, and are administratively and/or geographically centralized. An interactive-form information-collection process generally is controlled from a server computer.
Unfortunately traditional cache management policies can have the effect of turning read dominated access patterns, which is the most general case, into write dominated access patterns for the caching device. This is detrimental in terms of device lifespan as well as device performance if the cache device is FLASH based.